package algorithm.leetcode.I601to800;

public class Q647 {

    public int countSubstrings(String s) {
        boolean[][] isHuiWen = new boolean[s.length()][s.length()];
        int totalHuiWen = 0;

        // 从下至上
        for (int i = s.length()-1; i >= 0; i--) {
            // 从左至右
            for (int j = i; j < s.length(); j++) {
                if (i == j) isHuiWen[i][j] = true;
                else if (j - i == 1) isHuiWen[i][j] = s.charAt(i) == s.charAt(j);
                else isHuiWen[i][j] = isHuiWen[i+1][j-1] && s.charAt(i) == s.charAt(j);
                if (isHuiWen[i][j]) totalHuiWen++;
            }
        }
        return totalHuiWen;
    }

    public static void main(String[] args) {
        Q647 q647 = new Q647();
        q647.countSubstrings("abc");
    }

}
